package codetop.huawei.T316;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: 18362
 * @Create: 2022-09-12 1:19:16 星期一
 */
class Solution {
    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++)
            last[s.charAt(i) - 'a'] = i;
        boolean[] used = new boolean[26];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            while (!stack.isEmpty()) {
                char d = s.charAt(stack.peek());
                if (c == d) {
                    stack.pop();
                    stack.push(i);
                    break;
                }
                if (used[c - 'a'])
                    break;
                if (c > d || last[d - 'a'] < i)
                    break;
                used[d - 'a'] = false;
                stack.pop();
            }
            if (!used[c - 'a']) {
                stack.push(i);
                used[c - 'a'] = true;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty())
            sb.append(s.charAt(stack.removeLast()));
        return sb.toString();
    }
}
